#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

// 数组实现 二叉树
char *createTree(unsigned int depth)
{
    // 函数内部的变量在栈内存上, 必须是静态的. 是常量 char[] 值不能改
    static char empty[0];
    if (depth == 0)
    {
        return empty;
    }

    int nodeNum = (int)pow(2, depth) - 1;
    //
    char *array = (char *)malloc(nodeNum * sizeof(char));

    // printf("-----%d\n", __LINE__);
    char ch;
    for (int i = 0; i < nodeNum; i++)
    {
        ch = getchar();
        if (ch == '\n')
        {
            break;
        }
        array[i] = ch;
    }
    return array;
}

void root(char *tree, char key)
{
    tree[0] = key;
}

void setLeft(char *tree, char key, int parent)
{
    printf("------>setLeft index=%d, value=%c\n", (parent * 2) + 1, key);
    tree[(parent * 2) + 1] = key;
}

void setRight(char *tree, char key, int parent)
{
    printf("------>setRight index=%d, value=%c\n", (parent * 2) + 2, key);
    tree[(parent * 2) + 2] = key;
}

// 打印二叉树
void printTree(char *tree)
{
    // BUG:这里的长度值是不固定
    printf("tree length>> %lu\n", strlen(tree));
    int len = strlen(tree);
    // 计算出 满二叉树的结点
    int expect = pow(2, ((len + 1) / 2 + 1));
    // 计算 二叉的树高
    int depth = log2(expect);
    // printf("predict length>> %d, depth=%d\n", expect, depth);

    int blankNum = depth, eachNum;
    int j = 0;
    for (int i = 0; i < depth; i++)
    {
        // printf("----->%d\n", i);
        eachNum = pow(2, i);

        int count = 0;
        while (count < eachNum && j <= len)
        {
            //  || (count != 0 && count % 2 == 0)
            if ((i + 1) != depth && count == 0)
            {
                printf("---");
            }
            char cur = tree[j + count];
            // printf("value=%d", cur);
            // 虚拟结点
            if (!(cur >= 'a' && cur <= 'z' || cur >= 'A' && cur <= 'Z' || cur >= '0' && cur <= '9'))
            {
                cur = '@';
            }
            printf("%*s%c", blankNum, "  ", cur);
            count++;
        }
        printf("\n");

        blankNum--;
        j = j + eachNum;
    }
}

int main(){

    char myTree[10];
    root(myTree, 'A');
    setLeft(myTree, 'B', 0);
    setRight(myTree, 'C', 0);
    setLeft(myTree, 'D', 1);
    setRight(myTree, 'E', 1);
    setLeft(myTree, 'G', 2);
    setRight(myTree, 'F', 2);
    // BUG: strlen myTree 的值是随机的？
    printf("myTree len=%lu\n", strlen(myTree));
    printTree(myTree);

    exit(0);
    char *trees = createTree(3);
    printTree(trees);
    printf("--->the trees length = %lu\n", strlen(trees));

    return 0;
}